package com.sort;

import java.util.Arrays;

/**
 * 插入排序
 */


public class InsertSort implements Sort {

    public static void main(String[] args) {
        int[] arr = {
                1, 2, 4, 3, 56, 456, 78, 9123, 4565, 45,1, 2, 4, 3, 56, 456, 78, 9123, 4565, 45
        };

        for (int j : arr) {
            System.out.print(j + "\t");
        }
        System.out.println();

        int[] run = new InsertSort().run(arr);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(run[i] + "\t");
        }

    }

    @Override
    public int[] run(int[] arr) {
//        拷贝数组内容 不对原数组 产生改变
        int[] ar = Arrays.copyOf(arr, arr.length);

//            从第二个到最后一个都是待排序的
        for (int i = 1; i < ar.length; i++) {
//            记录插入的数据
            int temp = ar[i];

//            记录要插入的位置的index
            int j = i;

//            交换数据
            while (j > 0 && temp < ar[j - 1]) {
                ar[j] = ar[j - 1];
                j--;
            }

//          if为了稳定性
            if (j != i) {
                ar[j] = temp;
            }
        }
        return ar;
    }
}
